package ljl.alg.jianzhioffer.round2;

import commons.TreeNode;

/**
 * 公共祖先，二叉搜索树
 * 有序没序的，都是不会做
 * */
public class _68_1_bi_search_tree_common_ancestor {
    
    // 1. 两个数都比 root 大，root = root.right
    // 2. 小，left
    // 3. 否则，root 就是答案
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (p.val > q.val)
            return lowestCommonAncestor2(root, q, p);
        while (true) {
            if (root.val > q.val) root = root.left;
            else if (root.val < p.val) root = root.right;
            else return root;
        }
    }
    
    // 递归同理
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (p.val > q.val)
            return lowestCommonAncestor(root, q, p);
        if (root.val < p.val)
            return lowestCommonAncestor(root.right, p, q);
        if (root.val > q.val)
            return lowestCommonAncestor(root.left, p, q);
        return root;
    }
    
}
